<!DOCTYPE HTML>

<!-- 
Strata by HTML5 UP
html5up.net | @n33co
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
	<head>
		<title>Floyd &middot; Blog for Ysc</title>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />
		<meta name="author" content="Your name">
		<meta name="description" content="Describe your website">
		<meta http-equiv="content-language" content="en-us" />

		
		<meta name="og:site_name" content="Blog for Ysc">
		<meta name="og:title" content="Floyd">
		<meta name="og:url" content="https://yeeeesc.gitee.io/post/floyd/">
		
		<meta name="og:image" content="https://yeeeesc.gitee.io/images/avatar.jpg">
		
		

		<meta name="generator" content="Hugo 0.69.2" />

		<!--[if lte IE 8]><script src='https://yeeeesc.gitee.io/js/ie/html5shiv.js'></script><![endif]-->
		<link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
		<link rel="stylesheet" href="https://yeeeesc.gitee.io/css/main.css" />
		<!--[if lte IE 8]><link rel="stylesheet" href="https://yeeeesc.gitee.io//css/ie8.css"><![endif]-->

		
		
	</head>

	<body id="top">
		<!-- Header -->
<header id="header">
	
	<a href="https://yeeeesc.gitee.io/" class="image avatar"><img src="https://yeeeesc.gitee.io/images/avatar.jpg" alt="" /></a>
	
	
		<h1><strong>I&rsquo;m Strata</strong>, a super simple<!-- raw HTML omitted --> responsive site template freebie<!-- raw HTML omitted --> crafted by <a href="//html5up.net">HTML5 UP</a>.</h1>
	

	
		<nav id="sidebar">
			<ul>
			
				<li><a href="https://yeeeesc.gitee.io/">Home</a></li>
			
				<li><a href="https://yeeeesc.gitee.io/post/">Blog</a></li>
			
			</ul>
		</nav>
	
</header>


		<!-- Main -->
		<div id="main">
			
	<span>
		<h1>Floyd</h1>

		<i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-19 13:39:46 &#43;0200 &#43;0200">2020-10-19</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/algorithm">Algorithm</a>
        
        
    



   
   


	</span>

	<p>
	    <h3 id="step-1-思路">Step 1. 思路</h3>
<p>假设图上的任意两个点，已知两点间的路径权值，如果在图中能够找到一个点, 使其成为两点间的桥点，并且构成的新路径值小于旧路径值。则新路比旧路更短，由此可以得到一个递推公式：</p>
<p><strong>d[u][v]=min(d[u][v],d[u][k]+d[k][v])</strong></p>
<h3 id="step-2-代码实现">Step 2. 代码实现</h3>
<pre><code>for (int k = 1; k &lt;= n; k++)
	for (int i = 1; i &lt;= n; i++)
		for (int j = 1; j &lt;= n; j++)
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
</code></pre><h3 id="step-3-潜在疑惑">Step 3. 潜在疑惑</h3>
<p>由于<code>d[i][k]</code>，<code>d[k][j]</code>在不断更新，而不是恒定的最小值，所以如何保证<code>d[i][j]</code>在最后一次更新的时候，<code>d[i][k]</code>，<code>d[k][j]</code>一定是最小的 ?</p>
<ol>
<li>令任意两点i和j之间的路径上可选择经过的结点集合中，桥点编号最大的是k，当k=x的时候，<code>d[i][j]</code>得到最小值。</li>
<li>设i-x中的桥点编号最大的为x1 ,x-j中编号最大的为x2</li>
<li>易得x&gt;x1 ,x&gt;x2①</li>
<li>假设此时命题成立，则x=$x_1$时，<code>d[i][x]</code>最小，x=x2 时，<code>d[x][j]</code>最小</li>
<li>由此可以得到x=k的时候<code>d[i][x]+d[x][j]</code>已经是最小了,那么<code>e[i][j]=min(e[i][j]，e[i][x]+e[x][j])</code>必然可以得到最小值</li>
</ol>
<h3 id="step-4-原先的错误想法以及更正">Step 4. 原先的错误想法以及更正</h3>
<p>假设x1 &gt; k ，当 x = k，由于<code>d[i][k]</code> 还未取得最小值, 故<code>d[i][k] + d[k][j]</code>并没有取到最大值。所以命题①错误？事实上因为i-j的桥点编号最大的必然是k，此时令 k = x1 , 则 <code>d[i][k]</code>的桥点编号皆小于k, 故当 x = k 时，<code>d[i][k]</code>和<code>d[k][j] </code> ，因此<code>f[i][j]</code>可以取到最大值。 当 x2 &gt; k 时同理。</p>

	</p>

	<div id="disqus_thread"></div>
<script type="application/javascript">
    var disqus_config = function () {
    
    
    
    };
    (function() {
        if (["localhost", "127.0.0.1"].indexOf(window.location.hostname) != -1) {
            document.getElementById('disqus_thread').innerHTML = 'Disqus comments not available by default when the website is previewed locally.';
            return;
        }
        var d = document, s = d.createElement('script'); s.async = true;
        s.src = '//' + "spf13" + '.disqus.com/embed.js';
        s.setAttribute('data-timestamp', +new Date());
        (d.head || d.body).appendChild(s);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

		</div>

		<!-- Footer -->
<footer id="footer">
	<ul class="icons">
		
		
		
		<li><a href="//twitter.com/spf13" target="_blank" class="icon fa-twitter"><span class="label">Twitter</span></a></li>
		
		
		<li><a href="//github.com/spf13" target="_blank" class="icon fa-github"><span class="label">GitHub</span></a></li>
		
		
		<li><a href="//gitlab.com/spf13" target="_blank" class="icon fa-gitlab"><span class="label">GitLab</span></a></li>
		
		
		
		
		
		<li><a href="https://yeeeesc.gitee.io/#contact-form" class="icon fa-envelope-o"><span class="label">Email</span></a></li>
		
		
		<li><a href="https://yeeeesc.gitee.io/index.xml" class="icon fa-rss" type="application/rss+xml"><span class="label">RSS</span></a></li>
		
	</ul>

	<ul class="copyright">
		
		<li>© John Doe</li>
		
		<li>Design: <a href="//html5up.net">HTML5 UP</a></li>
		
		<li>Demo Images: <a href="//unsplash.com/">Unsplash</a></li>
		
	</ul>
</footer>

<!-- Scripts -->
<script src="https://yeeeesc.gitee.io/js/jquery.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/jquery.poptrox.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/skel.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/util.js"></script>

<script src="https://yeeeesc.gitee.io/js/main.js"></script>





	</body>
</html>
